package puzzle.nurikabe.data;

import java.util.ArrayList;
import java.util.List;

import puzzle.common.data.AbstractBoard;
import puzzle.common.data.HatanException;
import puzzle.common.point.Direction;
import tomoto.assertion.ParamUtil;
import tomoto.util.ArrayUtil;
import tomoto.util.BitUtil;

public class NurikabeBoard extends AbstractBoard<NurikabeBoard> {
	private int[] m_boardStates;
	private List<ShimaState> m_shimaStates;
	private boolean[] m_isAssumedFlags;
	private int m_nextKabeNumber;
	private int m_nextUndeterminedShimaNumber;

//	private boolean[] m_isDirtyFlags;
//	private boolean[] m_isDirtyFlagsBuf;

//	private int m_assumedClosureNumber;
//	private int[] m_closureNumbers;

	public NurikabeBoard(int w, int h) {
		super(w, h);
		m_boardStates = new int[w * h];
		m_shimaStates = new ArrayList<ShimaState>();
		m_isAssumedFlags = new boolean[w * h];
		m_nextKabeNumber = -1;
		m_nextUndeterminedShimaNumber = StateUtil.UNDETERMINED_SHIMA_BASE;

//		m_isDirtyFlags = new boolean[w * h];
//		Arrays.fill(m_isDirtyFlags, true);
//		m_isDirtyFlagsBuf = new boolean[w * h];
	}

	public NurikabeBoard(NurikabeBoard other) {
		super(other);
		m_boardStates = ArrayUtil.dup(other.m_boardStates);

		m_shimaStates = new ArrayList<ShimaState>();
		for (ShimaState s : other.m_shimaStates) {
			m_shimaStates.add(s.dup());
		}

		m_isAssumedFlags = ArrayUtil.dup(other.m_isAssumedFlags);
		m_nextKabeNumber = other.m_nextKabeNumber;
		m_nextUndeterminedShimaNumber = other.m_nextUndeterminedShimaNumber;

//		m_isDirtyFlags = ArrayUtil.dup(other.m_isDirtyFlags);
//		m_isDirtyFlagsBuf = ArrayUtil.dup(other.m_isDirtyFlagsBuf);
	}

	@Override
	protected void copyFromImpl(NurikabeBoard other) {
		ArrayUtil.copy(other.m_boardStates, m_boardStates);

		m_shimaStates.clear();
		for (ShimaState s : other.m_shimaStates) {
			m_shimaStates.add(s.dup());
		}

		ArrayUtil.copy(other.m_isAssumedFlags, m_isAssumedFlags);
		m_nextKabeNumber = other.m_nextKabeNumber;
		m_nextUndeterminedShimaNumber = other.m_nextUndeterminedShimaNumber;

//		ArrayUtil.copy(other.m_isDirtyFlags, m_isDirtyFlags);
//		ArrayUtil.copy(other.m_isDirtyFlagsBuf, m_isDirtyFlagsBuf);
	}

	@Override
	public NurikabeBoard dup() {
		return new NurikabeBoard(this);
	}

	@Override
	public void snapshotDirtyFlags() {
		for (ShimaState s : m_shimaStates) {
			s.snapshotDirtyFlag();
		}
		
//		ArrayUtil.copy(m_isDirtyFlagsBuf, m_isDirtyFlags);
//		for (int i = 1; i < m_isDirtyFlags.length; i++) {
//			m_isDirtyFlags[i] |= m_isDirtyFlagsBuf[i - 1];
//		}
//		for (int i = 0; i < m_isDirtyFlags.length - 1; i++) {
//			m_isDirtyFlags[i] |= m_isDirtyFlagsBuf[i + 1];
//		}
//		for (int i = m_isDirtyFlags.length - 1; i >= width; i--) {
//			m_isDirtyFlags[i] |= m_isDirtyFlags[i - width];
//		}
//		for (int i = width; i < m_isDirtyFlags.length; i++) {
//			m_isDirtyFlags[i - width] |= m_isDirtyFlags[i];
//		}
	}
	
//	public boolean isDirty(int x, int y) {
//		return m_isDirtyFlags[x + y * width];
//	}

	public void addShima(int x, int y, int n) {
		ShimaState s = new ShimaState(m_shimaStates.size() + 1, n, x, y, width, height);
		m_shimaStates.add(s);
		setBoardState(x, y, s.i);

		for (int i = 0; i < m_shimaStates.size() - 1; i++) {
			ShimaState s1 = m_shimaStates.get(i);
			s.setForbiddenAround(s1.p.x, s1.p.y);
			s1.setForbiddenAround(x, y);
		}

	}

	private boolean setBoardState(int x, int y, int n) {
		assert inRange(x, y);
		int i = x + y * width;
		if (m_boardStates[i] != n) {
			m_boardStates[x + y * width] = n;
//			m_isDirtyFlagsBuf[x + y * width] = true;
			return true;
		} else {
			return false;
		}
	}

	public int getBoardState(int x, int y) {
		if (inRange(x, y)) {
			return m_boardStates[x + y * width];
		} else {
			return StateUtil.OUT_OF_BOARD;
		}
	}

	public ShimaState getShimaState(int i) {
		ParamUtil.check(i > 0);
		if (StateUtil.isDeterminedShima(i)) {
			return m_shimaStates.get(i - 1);
		} else {
			return null;
		}
	}

	public boolean setKabe(int x, int y) throws HatanException {
		int n0 = getBoardState(x, y);
		if (n0 < 0) {
			return false;
		} else if (n0 > 0) {
			throw new HatanException();
		}
		assert n0 == 0;

		checkCrusterAround(x, y);

		boolean isChanged = false;

		for (int n1 : getNeighborStates(x, y)) {
			if (StateUtil.isRealKabe(n1)) {
				if (n0 == 0) {
					n0 = n1;
				} else {
					isChanged |= replace(n1, n0);
				}
			}
		}

		if (n0 == 0) {
			n0 = getAvailableKabeNumber();
		}

		isChanged |= setBoardState(x, y, n0);

		setShimaForbidden(x, y);

		return isChanged;
	}

	private void checkCrusterAround(int x, int y) throws HatanException {
		int flag = 0;
		for (Direction d : Direction.CLOCKWISE8) {
			int n = getBoardState(x + d.v.dx, y + d.v.dy);
			flag = (flag << 1) | (StateUtil.isRealKabe(n) ? 1 : 0);
		}

		if (BitUtil.isAllBitsSet(flag, 0xe0) || BitUtil.isAllBitsSet(flag, 0x38)
				|| BitUtil.isAllBitsSet(flag, 0x0e) || BitUtil.isAllBitsSet(flag, 0x8e)) {
			throw new HatanException();
		}
	}

	public boolean setShima(int x, int y) throws HatanException {
		int n = getBoardState(x, y);
		if (n > 0) {
			return false;
		} else if (n < 0) {
			throw new HatanException();
		}

		return setShimaAux(x, y, decideShimaNumber(x, y));
	}

	public boolean updateShima(int x, int y, int n) throws HatanException {
		return setShimaAux(x, y, n);
	}

	private boolean setShimaAux(int x, int y, int n) throws HatanException {
		assert getBoardState(x, y) == 0 || StateUtil.isUndeterminedShima(getBoardState(x, y));

		boolean isChanged = false;

		if (setBoardState(x, y, n)) {
			isChanged = true;

			if (StateUtil.isDeterminedShima(n)) {
				ShimaState s = getShimaState(n);
				s.incrementArea();
				s.confirm(x, y);
				setOtherShimasForbiddenAround(x, y, n);
			} else {
				int n1 = StateUtil.decodeOwningShima(n);
				if (n1 != 0) {
					ShimaState s = getShimaState(n1);
					s.confirm(x, y);
					setOtherShimasForbiddenAround(x, y, n1);
				}
			}
			propagateDeterminedShima(x, y, n);
		}

		return isChanged;
	}

	private boolean setOtherShimasForbiddenAround(int x, int y, int n) throws HatanException {
		ShimaState s0 = getShimaState(n);
		boolean isChanged = false;

		for (Direction d : Direction.CLOCKWISE4) {
			int x1 = x + d.v.dx;
			int y1 = y + d.v.dy;
			for (ShimaState s : m_shimaStates) {
				if (s != s0) {
					isChanged |= s.setForbidden(x1, y1);
				}
			}
		}

		return isChanged;
	}

	private void setShimaForbidden(int x, int y) {
		for (ShimaState s : m_shimaStates) {
			s.setForbidden(x, y);
		}
	}

	private boolean propagateDeterminedShima(int x, int y, int n0) throws HatanException {
		boolean isChanged = false;

		for (Direction d : Direction.CLOCKWISE4) {
			int x1 = x + d.v.dx;
			int y1 = y + d.v.dy;
			int n = getBoardState(x1, y1);
			if (n <= 0) {
				// just ignore
			} else if (StateUtil.isDeterminedShima(n)) {
				// just ignore, but make sure if it can contact here
				if (n != n0) {
					throw new HatanException();
				}
			} else {
				if (n != n0) {
					isChanged |= setShimaAux(x1, y1, n0);
					isChanged |= propagateDeterminedShima(x1, y1, n0);
				} else {
					// just ignore
				}
			}
		}

		return isChanged;
	}

	private int decideShimaNumber(int x, int y) throws HatanException {
		int determinedNeighbor = 0;
		int undeterminedNeighbor = 0;
		for (int n : getNeighborStates(x, y)) {
			if (StateUtil.isDeterminedShima(n)) {
				if (determinedNeighbor == 0) {
					determinedNeighbor = n;
				} else {
					if (determinedNeighbor != n) {
						throw new HatanException();
					}
				}
			} else if (StateUtil.isUndeterminedShima(n)) {
				if (undeterminedNeighbor == 0) {
					undeterminedNeighbor = n;
				}
			}
		}

		if (determinedNeighbor != 0) {
			return determinedNeighbor;
		} else if (undeterminedNeighbor != 0) {
			return undeterminedNeighbor;
		} else {
			return getAvailableUndeterminedShimaNumber();
		}
	}

	private boolean replace(int from, int to) {
		boolean isChanged = false;
		for (int i = 0; i < m_boardStates.length; i++) {
			if (m_boardStates[i] == from) {
				m_boardStates[i] = to;
				isChanged = true;
			}
		}
		return isChanged;
	}

	private int getAvailableKabeNumber() {
		return m_nextKabeNumber--;
	}

	private int getAvailableUndeterminedShimaNumber() {
		return m_nextUndeterminedShimaNumber++;
	}

	private int[] getNeighborStates(int x, int y) {
		return new int[] { getBoardState(x, y - 1), getBoardState(x + 1, y),
				getBoardState(x, y + 1), getBoardState(x - 1, y), };
	}

	public List<ShimaState> getShimaStates() {
		return m_shimaStates;
	}

	public boolean isAssumed(int x, int y) {
		return m_isAssumedFlags[x + y * width];
	}

	public void setAssumed(int x, int y) {
		m_isAssumedFlags[x + y * width] = true;
	}

	// 指紋を使わなければ不要
//	@Override
//	public Object getFingerPrint() {
//		FastBitSet digest = new FastBitSet(m_boardStates.length);
//		for (int i = 0; i < m_boardStates.length; i++) {
//			digest.set(i, m_boardStates[i] < 0);
//		}
//		return digest;
//	}

	// 部分解をやらなければ不要
//	public int getAssumedClosureNumber() {
//		return m_assumedClosureNumber;
//	}
//
//	public int[] getClosureNumbers() {
//		return m_closureNumbers;
//	}
//
//	public void setAssumedClosureInfo(int assumedClosureNumber, int[] closureNumbers) {
//		m_assumedClosureNumber = assumedClosureNumber;
//		m_closureNumbers = closureNumbers;
//	}
}
